﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SortingAlgorthm.Implementation
{
    public class Merge<T> : Algorithm<T>
    {
        public override void Sort(IList<T> list)
        {
            IList<T> tempList = _Sort(list, 0, list.Count);
            for (int i = 0; i < list.Count; i++)
            {
                list[i] = tempList[i];
            }
        }
        private IList<T> _Sort(IList<T> list, Int32 start, Int32 end)
        {
            int middle = (end + start) / 2;
            if (start == middle)
            {
                return new T[] { list[start] };
            }
            else
            {
                var list1 = _Sort(list, start, middle);
                var list2 = _Sort(list, middle, end);
                return _Merge(list1, list2);
            }
        }
        private IList<T> _Merge(IList<T> list1, IList<T> list2)
        {
            List<T> result = new List<T>();
            int i1 = 0, i2 = 0;
            while (i1 < list1.Count && i2 < list2.Count)
            {
                if (Comparer.Compare(list1[i1], list2[i2]) < 0)
                {
                    result.Add(list1[i1]);
                    i1++;
                }
                else
                {
                    result.Add(list2[i2]);
                    i2++;
                }
            }
            IList<T> left = null;
            int start = 0;
            if (i1 == list1.Count)
            {
                start = i2;
                left = list2;
            }
            else
            {
                start = i1;
                left = list1;
            }
            for (int i = start; i < left.Count; i++)
                result.Add(left[i]);
            return result;
        }
    }
}
